package hot;

public class yiersi {
//    https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/?envType=study-plan-v2&envId=top-100-liked
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static int max=-0x3f3f3f3f;
    public static int maxPathSum(TreeNode root) {
        //每次进来重置max
        max=-0x3f3f3f3f;
        dfs(root);
        return max;
    }
    public static int dfs(TreeNode root){
        if(root==null){
            return 0;
        }
        //如果左子树的和为0 就直接不选
        int leftSum=Math.max(0,dfs(root.left));
        int  rightSum=Math.max(0,dfs(root.right));
        int currentSum=root.val+leftSum+rightSum;
        max=Math.max(currentSum,max);
        return root.val+Math.max(leftSum,rightSum);


    }

    public static void main(String[] args) {
        TreeNode treeNode1=new TreeNode(1);
        TreeNode treeNode2=new TreeNode(2);
        TreeNode treeNode3=new TreeNode(3);
        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;
//        int i = maxPathSum(treeNode1);
        int dfs = dfs(treeNode1);
        System.out.println(dfs);
        System.out.println(max);


    }
    }

